#define _CRT_SECURE_NO_WARNINGS 1



#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
struct BinaryTreeNode;
typedef  struct BinaryTreeNode* QDataType;

typedef struct QueNode
{
	struct QueNode* next;
	QDataType val;
}QN;

typedef struct Queue
{
	QN* head;
	QN* tail;
	int sz;
}Queue;

void Queueinit(Queue* q);

void QueueDestory(Queue* q);

bool QueueEmpty(Queue* q);

void QueuePop(Queue* q);

void QueuePush(Queue* q, QDataType x);

QDataType Queuefront(Queue* q);

QDataType Queuetail(Queue* q);

int QueueSize(Queue* q);

void Queueinit(Queue* q)
{
	assert(q);
	q->head = NULL;
	q->tail = NULL;
	q->sz = 0;
}

void QueueDestory(Queue* q)
{
	assert(q);
	QN* tmp = q->head;
	while (tmp)
	{
		QN* next = tmp->next;
		free(tmp);
		tmp = next;
	}
	q->tail = q->head = NULL;
	q->sz = 0;
	free(q);
}

bool QueueEmpty(Queue* q)
{
	assert(q);
	return q->head == NULL
		&& q->tail == NULL;
}

void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	if (q->head->next == NULL)
	{
		free(q->head);
		q->head = q->tail = NULL;
	}
	else
	{
		QN* tmp = q->head->next;
		free(q->head);
		q->head = tmp;
	}
	q->sz--;
}

void QueuePush(Queue* q, QDataType x)
{
	assert(q);

	QN* newnode = (QN*)malloc(sizeof(QN));
	if (!newnode)
		perror("malloc file");
	newnode->val = x;
	newnode->next = NULL;
	if (q->head == NULL)
	{
		q->head = q->tail = newnode;
	}
	else
	{
		q->tail->next = newnode;
		q->tail = newnode;
	}
	q->sz++;
}

QDataType Queuefront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->head->val;
}

QDataType Queuetail(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->tail->val;
}

int QueueSize(Queue* q)
{
	assert(q);
	return q->sz;
}